The Hough transform is a widely known and effective method for detecting and measuring extended straight lines in images in the presence of noise and discontinuities.
In U.S. Pat. No. 3,069,654, issued Dec. 18, 1962, "Method and Means for Recognizing Complex Patterns", P.V.C. Hough discloses method and apparatus for dividing a viewed image representation into sufficiently small sectors such that a complex pattern is divided into substantially straight line segments. Each straight line segment is detected and transformed into slope-intercept data for detecting the presence of patterns within the image.
In Duda and Hart's classical formulation of the Hough transform for Cartesian image domains ("Use of the Hough Transform to Detect Lines and Curves in Pictures", Communications of the ACM, pp.11-15, January, 1972) a straight line (L.sub.1 in FIG 1a) is transformed into a point (H(L.sub.1) in FIG. 1b) in a space whose coordinates are the orientation and position parameters of the line. A point in the Cartesian domain (P.sub.2 in FIG. 1a) is transformed into a Hough domain sine curve (H(P.sub.2) in FIG. 1b) whose constituent points correspond to the orientation-position combinations consistent with all possible lines through the Cartesian domain point. A set of Cartesian domain points transforms to a set of Hough domain sine curves, which intersect at a single point if the Cartesian points are collinear.
Points P.sub.3, P.sub.4, and P.sub.5 in FIG. 1a are collinear; their corresponding sine curves in FIG. 1b intersect at the point labelled H(P.sub.3, P.sub.4, P.sub.5). Thus, a duality relates Cartesian domain points to Hough domain sine curves, and Hough domain points to Cartesian domain straight lines. The Cartesian and Hough domains are distinct entities with distance geometries. The Hough domain serves as a two dimensional histogram which sorts candidate points based on the families of lines with which they are consistent, and statistically pools collinear Cartesian points by tallying coincident loci of their corresponding sine curves. Maximal peaks correspond to the recognized lines.
In U.S. Pat. No. 4,267,573, issued May 12, 1981, "Image Processing System", G. Chaikin and the present inventor disclose an image processing system having imaging sensors arranged in a polar exponential array geometry. This sensor geometry, also known as log spiral, conformal logarithmic and polar exponential grid (PEG) has been successfully applied in a number of imaging applications.
In an article entitled "Exponential Sensor Array Geometry and Simulation" presented at a conference on Digital and Optical Shape Representation and Pattern Recognition, Proceedings of SPIE, Apr. 4-6, 1988, the present inventor discusses the geometric relations between polar exponential sensor geometry and ordinary Cartesian image sensor geometry The conversion between ordinary Cartesian image coordinates and the natural log-polar coordinate of polar exponential sensor arrays is termed "log-polar mapping" hereinafter, and imagery represented in such coordinates is termed "log-polar imagery".
Despite the great utility of the Hough transform and known variants thereof for image processing applications several disadvantages are known to exist. One significant disadvantage relates to an inability to apply the Hough transform locally, such as directly at a plane of image sensors. Instead, electronic buses and other circuitry are required to export the image data to off-sensor plane image processing electronics for Hough transform processing.
Another disadvantage of the Hough transform is that the Hough transform coordinate system is totally different than the image coordinate system. Thus, there must be computational conversion between the two coordinate systems. Furthermore, the inherently discrete sampling properties of the image sensor transform to complicated digitization errors in the Hough representation.
It is thus an object of the invention to provide a geometric coordinate representation which is identical for both image and Hough domains, and a simplified method for executing a Hough transform within this unified coordinate system.
It is another object of the invention to provide for a simplification of image processing apparatus and method over conventional Hough transform-related techniques.
It is another object of the invention to provide apparatus and method for executing a log-Hough transform technique.
It is another object of the invention to provide a log-Hough transform method and apparatus that is amenable to integrated circuit fabrication techniques for "in-place" local image processing that eliminates a requirement for buses to export data away from image sensors to an external Hough domain.